Weighted Fair Queuing (WFQ) and credit token schemes are two ways to schedule packets out of a multi-queue system. With a WFQ scheme, each queue gets a transmission window and may forward packets only during its transmission window. The size of the transmission window given to each queue corresponds to the amount of bandwidth that has been allocated to the respective queues. With a credit token scheme, each queue gets tokens and may forward packets so long as the respective queue has tokens. The amount of tokens given to each queue corresponds to the amount of bandwidth that has been allocated to the respective queues.
With a WFQ scheme, time slots are allocated to each queue. The size of the time slots may be different. The bandwidth allocated to each queue can be weighted by setting the time slots to different sizes. An idle time slot allocation may be used to control the total bandwidth utilized.
With a credit token scheme, tokens are replenished for each queue at the start of a time period. The queues may forward packets as long as they have tokens. When more than one queue has tokens, packets from the queue with the highest priority are typically forwarded first. The length of the time periods between token replenishment may be adjusted to control the profile of bandwidth utilization.
With both the WFQ and credit token schemes, during a given time period a queue may not use all of its allocated bandwidth. Accordingly, it would be desirable to identify which queues can borrow unused allocated bandwidth from a queue that does not utilize its allocated share, such as when the queue has no more packets. It would also be desirable to determine at what rate those queues are entitled to forward packets.
In view of the desire to borrow unused allocated bandwidth from a queue that does not utilize its allocated share of bandwidth, what is needed is a new unused bandwidth allocation scheme that allows determination of which queues can borrow unused allocated bandwidth. In addition, it would be advantageous to establish a rate at which those queues are entitled to forward packets.